1. Technical Field
The present invention relates to a device, a method, and a program for estimating a quality-degraded location of a communication network, and a communication network system, in particular, to a system for estimating a degraded location in communication quality of a network from flow quality information corresponding to multi-paths routing.
2. Background Art
In a communication network, in order to identify a communication quality-degraded location at high speed at the time communication quality is degraded, a number of monitoring devices are allocated in the network so as to continuously monitor the communication quality at locations the monitoring devices are allocated. Then, at the time the communication quality is degraded, a section with degraded quality is estimated based on a position of the monitoring device at which the quality degradation occurs. In this system, there is a problem that a number of monitoring devices are necessary in order to increase estimation accuracy of a position where quality is degraded, and cost for allocating such monitoring devices is high. In order to handle this problem, as a related art, there is a system for estimating a quality-degraded location from routing information and quality information of a communication flow passing through a network (refer to, JP-A-2006-238052). Hereinafter, description will be made with respect to this system.
First, a correspondence table (flow-link correspondence table) of flows, links (directed links) through which the flows pass, and quality is created. For example, flows F1 to F5 are assumed to pass through a network including routers (or packet switches) R1 to R6 as shown in FIG. 14. With respect to the network of FIG. 14, names are assigned to the links as shown in FIG. 15, and packet loss rates are used to show quality. Then, assuming that packet loss rates of the flows F1 to F5 are 3.0%, 2.5%, 3.5%, 1.0%, and 0.5%, respectively, the flow-link correspondence table is created as shown in FIG. 16. In this state, each flow is assumed to carry 100 packets per second, and a packet loss rate is determined based on an amount of packet loss for every 2 seconds.
Next, non-degraded link elimination processing is carried out. That is, on the basis of a degradation threshold value and non-degradation threshold value of flow quality set in advance, a flow with quality lower than the degradation threshold value is set to be a degraded flow, a flow with quality higher than the non-degradation threshold value is set to be a non-degraded flow, and a flow other than the above is set to be a middle quality flow. Then, a reduced flow-link correspondence table is created by eliminating a row of the middle quality flow, a row of the non-degraded flow, and a column of a link through which the non-degraded flow passes from the flow-link correspondence table. In the above example, for example, assuming that a packet loss rate of 2% is set to be a degradation threshold value and a packet loss rate of 1% is set to be a non-degradation threshold value, the flows F1 to F3 are degraded flows, the flow F5 is a non-degraded flow, and the flow F4 is a middle flow. Then, a reduced flow-link correspondence table is created in a manner that a row of the middle flow, a row of the non-degraded flow, and columns having a value of 1 in the row of the non-degraded flow are eliminated from the flow-link correspondence table. A state of the removal in the above example is shown in FIG. 17, and the reduced flow-link correspondence table is shown in FIG. 18.
Finally, a degraded location is estimated based on FIG. 18. For example, in an estimation method based on the number of quality-degraded flows, the numbers of flows with degraded quality that pass through links L10, L20, L50, and L40 are 1, 3, 1, and 1, respectively. Among the above links, the link L20 through which the largest number of flows pass is estimated as a degraded location.
Alternatively, a degraded location is estimated by a minimum link number estimation method described below.
In the minimum link number estimation method, a set of flows that pass through each of the links in FIG. 18 is considered. Then, a set of links that includes all the flows in FIG. 18 with a minimum number of links is determined, and such a set of links is set to be a set of degraded links. That is, in the example of FIG. 18, sets of flows that pass through links L10, L20, L50, and L40 are {F1}, {F1, F2, F3}, {F2}, and {F3}, respectively. For example, a sum-set of flows that pass through a set of links {L10, L50, L40} including three links is {F1, F2, F3}, and all the flows can be included. Other than the above, all the flows can be included by a set of links {L10, L20} including two links and by a set of link {L20} including one link. Among such sets of links that include all the flows, the set {L20} having the minimum number of links is estimated as a set of minimum links.
In the estimation system of a quality-degraded location by the related art described above, a link through which a flow passes is assumed to be able to be uniquely identified. However, in a network applied with multi-paths routing, load distribution routing, and the like, there are two or more paths that a flow may pass through. Therefore, there is a case where through which pass a flow actually passed cannot be identified. In such a case, the estimation system of a quality-degraded location by the related art cannot be applied.